#include "fstream"
#include <iostream>
#include <stack>
#include <string>

using namespace std;

stack<string> stk;
fstream       f;
int           cnt = 0;

string action[16][8] = {
    "S4",
    "0",
    "0",
    "0",
    "0",
    "0",
    "S5",
    "0",
    "0",
    "0",
    "0",
    "S6",
    "S7",
    "0",
    "0",
    "acc",
    "0",
    "r3",
    "S8",
    "r3",
    "r3",
    "S9",
    "0",
    "r3",
    "0",
    "r6",
    "r6",
    "r6",
    "r6",
    "r6",
    "0",
    "r6",
    "S4",
    "0",
    "0",
    "0",
    "0",
    "",
    "S5",
    "0",
    "0",
    "r8",
    "r8",
    "r8",
    "r8",
    "r8",
    "0",
    "r8",
    "S4",
    "0",
    "0",
    "0",
    "0",
    "0",
    "S5",
    "0",
    "S4",
    "0",
    "0",
    "0",
    "0",
    "0",
    "S5",
    "0",
    "S4",
    "0",
    "0",
    "0",
    "0",
    "0",
    "S5",
    "0",
    "S4",
    "0",
    "0",
    "0",
    "0",
    "0",
    "S5",
    "0",
    "0",
    "S15",
    "0",
    "S6",
    "S7",
    "0",
    "0",
    "0",
    "0",
    "r1",
    "S8",
    "r1",
    "r1",
    "S9",
    "0",
    "r1",
    "0",
    "r2",
    "S8",
    "r2",
    "r2",
    "S9",
    "0",
    "r2",
    "0",
    "r4",
    "r4",
    "r4",
    "r4",
    "r4",
    "0",
    "r4",
    "0",
    "r5",
    "r5",
    "r5",
    "r5",
    "r5",
    "0",
    "r5",
    "0",
    "r7",
    "r7",
    "r7",
    "r7",
    "r7",
    "0",
    "r7",
};
int    gotoarr[16][3] = {1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 2, 3, 0, 0, 0, 0, 11, 3, 0, 12, 3, 0, 0, 13, 0, 0, 14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
char   vt[8]          = {'(', ')', '*', '+', '-', '/', 'i', '#'};
string Production[8]  = {"E->E+T", "E->E-T", "E->T", "T->T*F", "T->T/F", "T->F", "F->(E)", "F->I"};
// string      action[12][6]  = {"S5", "0", "0", "S4", "0", "0", "0", "S6", "0", "0", "0", "acc", "0", "r2", "S7", "0", "r2", "r2", "0", "r4", "r4", "0", "r4", "r4", "S5", "0", "0", "S4", "0", "0", "0", "r6", "r6", "0", "r6", "r6", "S5", "0", "0", "S4", "0", "0", "S5", "0", "0", "S4", "0", "0", "0", "S6", "0", "0", "S11", "0", "0", "r1", "S7", "0", "r1", "r1", "0", "r3", "r3", "0", "r3", "r3", "0", "r5", "r5", "0", "r5", "r5"};
// int         gotoarr[12][3] = {1, 2, 3,0,0,0,0,0,0,0,0,0,8,2,3,0,0,0,0,9,3,0,0,10,0,0,0,0,0,0,0,0,0,0,0,0};
// char        vt[6]          = {'i', '+', '*', '(', ')', '#'};                           // 瀛樻斁缁堢粨绗�
char vn[3] = {'E', 'T', 'F'};   // 瀛樻斁闈炵粓缁撶
// string      Production[6]  = {"E->E+T", "E->T", "T->T*F", "T->F", "F->(E)", "F->i"};   // 浜х敓寮忛泦鍚�

int         com          = 0;
int         line         = 1;   // 璁板綍澶勭悊鐨勬楠ゆ暟
bool        flag         = false;
int         StatusNumber = 1;     // 鏍堜腑鐘舵€佹暟
string      StackString  = "#";   // 璁板綍绗﹀彿鏍堜腑鍐呭
int         Status[50]   = {0};   // 璁板綍鐘舵€佹爤
stack<char> Stack;                // 鍒涘缓涓€涓鍙锋爤
stack<int>  status;               // 鍒涘缓涓€涓姸鎬佹爤

void Judge(int& i, int j, const char arr[], char ch, string s)
{   // 鍒ゆ柇杈撳叆涓叉槸鍚︾敱鏂囨硶缁堢粨绗︾粍鎴�
    flag = false;
    for ( int l = 0; l < j; l++ ) {
        if ( ch == arr[l] ) {
            flag = true;
            i    = l;
            break;
        }
    }
    if ( !flag ) {
        cout << "\tError" << endl;
        com = s.size();
    }
}

void OutputStatus()
{   // 杈撳嚭鐘舵€侀泦
    for ( int i = 0; i < StatusNumber; i++ )
        cout << Status[i];
}

void OutputString(string s)
{   // 杈撳嚭鏈鐞嗙殑瀛楃涓�
    for ( int i = com; i < s.size(); i++ )
        cout << s.at(i);
}

void Output(string s)
{   // 杈撳嚭姝ラ銆� 鐘舵€侀泦銆� 绗﹀彿闆嗐€� 杈撳叆涓�
    cout << line << "\t";
    OutputStatus();
    cout << "\t" << StackString << "\t";
    OutputString(s);
    cout << "\t\t";
    line++;
}

void Shift(int i, string s)
{   // 绉昏繘鍑芥暟 S
    Output(s);
    cout << "ACTION[" << status.top() << "," << s.at(com) << "]=S" << i << ",状态" << i << "入栈" << endl;
    status.push(i);                          // 灏嗙姸鎬� i 鍘嬭繘状态
    Status[StatusNumber] = i;                // Status 璁板綍鐘舵€佹爤鐨勫唴瀹�
    Stack.push(s.at(com));                   // 灏嗗綋鍓嶉潰涓寸殑杈撳叆涓茬鍙峰帇杩涚鍙锋爤
    StackString = StackString + s.at(com);   // StackString 璁板綍绗﹀彿鏍堢殑鍐呭
    com++;                                   // 褰撳墠闈复鐨勮緭鍏ヤ覆瀛楃寰€鍚庣Щ涓€浣�
    StatusNumber++;                          // 鐘舵€佹暟鍔犱竴
}

void Goto(stack<int> st1, stack<char> st2, string s)
{   // GoTo 璇彞
    int  j   = -1;
    int  ch1 = st1.top();
    char ch2 = st2.top();
    Judge(j, 3, vn, ch2, s);   // 姹傚緱 ch2 鍦ㄩ潪缁堢粨绗﹁〃涓殑浣嶇疆
    if ( gotoarr[ch1][j] == 0 ) {
        cout << "\tError" << endl;
        com = s.size();
    }
    else {
        status.push(gotoarr[ch1][j]);   // 鏂扮姸鎬佽繘鏍�
        Status[StatusNumber] = gotoarr[ch1][j];
        StatusNumber++;
    }
}

void GrammarGuidedTranslation(int x) {
    // E->E+T规约
    string b = stk.top();
    stk.pop();
    string a = stk.top();
    stk.pop();
    char temp[10];
    for ( int i = 0; i < 10; ++i ) {
        temp[i] = '\0';
    }
    sprintf(temp, "T%d", cnt);
    cnt++;
    if ( x == 1 ) {
        f << "( " << cnt << " )  :  " << "+ " << a << " " << b << " " << temp << endl;
    }
    else if ( x == 4 ) {
        // r4:T->T*F规约
        f << "( " << cnt << " )  :  " << "* " << a << " " << b << " " << temp << endl;
    }
    else if ( x == 5 ) {
        // r5:T->T/F规约
        f << "( " << cnt << " )  :  " << "/ " << a << " " << b << " " << temp << endl;
    }
    else if ( x == 2 ) {
        // r2:E->E-T规约
        f << "( " << cnt << " )  :  " << "- " << a << " " << b << " " << temp << endl;
    }
    stk.push(temp);
}

void Reduction(int i, string s)
{
    // MYCODE
    if ( i == 1 || i == 2 || i == 4 || i == 5 ) {
        GrammarGuidedTranslation(i);
    }

    Output(s);
    cout << "r" << i << ":" << Production[i - 1] << "规约, GoTo(";
    int N = Production[i - 1].length() - 3;
    for ( int j = 0; j < N; j++ ) {   // 娑堥櫎瑕佸綊绾︾殑鐘舵€佸強绗﹀彿
        status.pop();
        Stack.pop();
        StatusNumber--;
        StackString.erase(StackString.length() - 1);
    }
    cout << status.top() << "," << Production[i - 1].at(0) << ")=";
    Stack.push(Production[i - 1].at(0));   // 绗﹀彿杩涙爤
    StackString = StackString + Stack.top();
    Goto(status, Stack, s);
    cout << status.top() << "入栈" << endl;
    Status[StatusNumber] = status.top();
}

void Analyse(string s)
{                      // 鍏蜂綋鍒嗘瀽鍑芥暟
    Stack.push('#');   // 鍒濆鍖�
    status.push(0);
    s     = s + "#";
    int t = -1;
    while ( com < s.size() ) {
        int  i  = status.top();
        char ch = s.at(com);
        /**
         * 这里用来将a,b,c都转换为i
         */
        if ( ch == 'a' || ch == 'b' || ch == 'c' ) {
            string string1;
            string1.push_back(ch);
            stk.push(string1);
            ch = 'i';
        }

        Judge(t, 8, vt, ch, s);
        if ( flag ) {
            if ( action[i][t] != "acc" && action[i][t] != "0" ) {
                if ( action[i][t].at(0) == 'S' ) {
                    action[i][t].erase(0, 1);               // 鍒犻櫎 action[i][t]鐨勯瀛楁瘝 S
                    Shift(atoi(action[i][t].c_str()), s);   // atoi(action[i][t].c_str())锛� 灏哸ction[i][t]杞崲涓烘暣鍨�
                    action[i][t].insert(0, "S");            // 灏� S 娣诲姞鍥� action[i][t]
                }
                else if ( action[i][t].at(0) == 'r' ) {
                    action[i][t].erase(0, 1);
                    // 只有在规约的时候，才有可能触发运算，所以在这里判断规约类型，然后输出运算结果
                    Reduction(atoi(action[i][t].c_str()), s);   // atoi(action[i][t].c_str())锛� 灏哸ction[i][t]杞崲涓烘暣鍨�
                    action[i][t].insert(0, "r");                // 灏� r 娣诲姞鍥� action[i][t]
                }
            }
            else if ( action[i][t] == "0" ) {
                cout << "\tError" << endl;
                break;
            }
            else if ( action[i][t] == "acc" ) {
                Output(s);
                cout << "acc" << "\t 分析成功" << endl;
                break;
            }
        }
        else if ( !flag ) {
            break;
        }
    }
}

int main()
{
    f.open("/home/libtity/complier/EXP5/output", ios::out);
    string s;
    cout << "推导规则" << endl;
    for ( int j = 0; j < 8; j++ )
        cout << Production[j] << endl;
    cout << "VT:" << endl;
    for ( int i = 0; i < 8; i++ )
        cout << vt[i] << " ";
    cout << endl;
    for ( int i = 0; i < 3; i++ )
        cout << vn[i] << " ";
    cout << endl;
    cout << "****************************LR(1)****************************" << endl;
    char T;
    cout << "Enter String" << endl;
    cin >> s;
    cout << "**************************Analyzer***************************" << endl;
    cout << "Step" << "\t" << "StateStack" << "\t" << "SymbolStack" << "\t" << "RemainingString" << "\t" << "Info"
         << endl;
    Analyse(s);
    com          = 0;
    line         = 1;
    StackString  = "#";
    StatusNumber = 1;
    while ( !Stack.empty() )
        Stack.pop();
    while ( !status.empty() )
        status.pop();
    return 0;
}